package com.wzl.algorithm;

/**
 * 快速排序，不稳定，因为车速太快（不是
 * 快速排序思路：
 * 1. 选取第一个数为基准
 * 2. 将比基准小的数交换到前面，比基准大的数交换到后面
 * 3. 对左右区间重复第二步，直到各区间只有一个数
 * 参考动画 1:40
 * https://www.bilibili.com/video/av39093184?from=search&seid=10229372650286177316
 *
 * @author weiZhiLin
 * @version 1.0
 * @date 2020/1/9 15:58
 */
public class QuickSort {
    public static int[] sort(int[] a) {
        int l = 0;
        int r = a.length - 2;
        int base = a.length - 1;
        quickSort(a, l, r, base);
        SortUtils.printArr(a);
        return a;
    }

    private static int[] quickSort(int[] a, int l, int r, int base) {
        // 不能写等于 防止便利到数组只有两个值的情况
        if (l > r) {
            return null;
        }
        while (l < r) {
            while (a[base] >= a[l] && l < r) {
                l++;
            }
            while (a[base] <= a[r] && l < r) {
                r--;
            }
            if (l < r) {
                // 打印一下 ヽ(￣▽￣)ﾉ
                // SortUtils.printEle(a,base);
                SortUtils.arraySwap(a, l, r);
            }
        }
        //判断一下
        if (a[base] < a[l]) {
            SortUtils.arraySwap(a, l, base);
        }
        // 注意这里的 base 是 l 而不是 l - 1
        quickSort(a, 0, l - 1, l );
        // 注意这里是 base 而不是 length
        quickSort(a, l + 1, base - 1, base);
        return a;
    }

}
